1. Field of the Invention
The present invention relates in general to secure communication. More particularly, it relates to the creation of encryption keys.
2. Background Art
Public key cryptosystems are ubiquitous in commerce, banking, and many government functions. Secure encrypted communication requires that an encryption key be 1) nondeterministic (i.e., random) and 2) securely distributed. Modem public key cryptosystems based on RSA or Diffie Hellmen for many years fulfilled both requirements and are elegant in their simplicity. Public key cryptosystems generally derive their security from the use of an encryption key that is based on the computational intractability of a mathematical problem (e.g., factoring or solving discrete logarithms).
However, brute force computational attacks have resulted in surprising success, most recently the factorization of a 193 digit integer in November 2005 using a configuration of 802.2 GHz Opteron processors over about a 6 month period. Additionally, quantum computers could exploit superposition to factor integers in polynomial time. Several approaches have been investigated for securely distributing random bit sequences (i.e., cryptographic keys) in a quantum-computing environment, including both mathematical operations not susceptible to attack by Shor's algorithm and quantum cryptography.
Cryptosystems that exploit physical one-way functions, instead of computationally unsolvable (by today's standards) math problems, would not be vulnerable to a computing attack—even those mounted by a quantum computer. Instead of being based on an algorithm that can be inverted, these systems exploit physical randomness that is only, to a high probability, observable to the legitimate communicating parties to establish the shared secret. There is therefore a need for cryptosystems that exploit physical layer randomness and security.
Quantum Cryptography
Quantum cryptography uses randomness at the physical layer to establish and distribute a secret. In quantum cryptography, the randomness extracted from the physical layer is based on ambiguity in the measured states of single photons. Quantum Key Distribution (QKD) is a form of quantum cryptography that originated in the work of Bennett and Brassard, Bennett, C. H. and G. Brassard, “Quantum cryptography: Public key distribution and coin tossing,” in Proceedings of the IEEE International Conference on Computers, Systems and Signal Processing, Bangalore, India, Dec. 10-12, 1984, pp. 175-179. This work resulted in the development of a cryptographic protocol, BB84. In the creation of this cryptographic protocol, information theory and quantum physics were wed together to bound the secrecy capacity of a quantum channel based on observable quantum bit error rate. As such, it is theoretically possible to guarantee that a third party would possess a vanishingly small amount of information about secret bits reconciled by the two communicating parties.
At the time of the writing of this patent document, BB84 is the most experimentally mature quantum cryptography protocol and offers unprecedented security guarantees. However, these security guarantees come with a cost. Generation and detection of single photons requires specialized equipment, and even the most capable experimental (and now commercial systems) are limited in range to about 75 kilometers of optical fiber. Free space optical QKD systems can close terrestrial links, but require a quiescent quantum channel, i.e. secret bit yields rapidly falls to zero in cases of precipitation, atmospheric turbulence and fog. There are other forms of quantum cryptography, including those based on Einstein, Polensky and Rosen (EPR) pairs. Physical realizations of these alternative protocols may offer certain advantages when compared to Bennett and Brassard protocol, but are subject to the same quiescent channel assumptions.
Wyner's Wiretap Channel
The concept of using attributes of the classical channel to establish a shared secret between two communicating parties originates with Wyner's [Wyner, A. D., “The Wire-Tap Channel,” Bell System Technical Journal, 54, pp. 1355-1387, October 1975.] seminal work on wire-tap channels.
Wyner considered the case where Station A and Station B communicate over a noisy channel. A eavesdropper may eavesdrop on that communication through a second channel that is also noisy. Wyner proved that Station A and Station B may agree on an encoding/decoding scheme that leaks only a small and bounded amount of information to the eavesdropper. In essence, as long as Station A and Station B have a signal-to-noise advantage over the eavesdropper, they may securely extract secret bits, placing an upper bound on the eavesdropper's knowledge; the greater the signal to noise advantage the greater the secrecy capacity. Wyner's original paper establishes a secrecy capacity for this scenario, analogous to the communication capacity in information theory.
Wyner's work influenced and motivated a variety of shared secret schemes that have since emerged. Ozarow and Wyner [Ozarow, L. H. and A. D. Wyner, “Wire-Tap Channel II,” Bell Labs Technical Journal, 63, pp. 2135-2157, December 1984.] considered the case where the eavesdropper is allowed to sample a set number of bits in the channel of Station A and Station B, as opposed to seeing some of the bits randomly. Ozarow and Wyner found that even in that case, it is possible to construct codes that bound the eavesdropper's knowledge.
Maurer and the Definition of Secrecy Efficiency
Maurer [Maurer, U., “Perfect Cryptographic Security from Partially Independent Channels,” Proceedings of the 23rd ACM Symposium on Theory of Computing (STOC), pp. 561-572, 1991.] also considers the general problem of Station A and Station B communicating secretly in the presence of the eavesdropper. Here the channel of Station A and Station B is independent of the eavesdropper's channel, though the latter channel may be less noisy (in contrast with the scenario considered in the Wyner work described above. Even if the eavesdropper's channel is less noisy, Station A and Station B may still communicate securely.
These results are expanded in Maurer, U., “Secret Key Agreement by Public Discussion,” IEEE Transactions on Information Theory, 39, No. 3, pp. 733-742, 1993. The notion of secrecy capacity is defined and used to achieve capacity bounds under general binary channels. One relevant finding by Maurer is that two-way communication between Station A and Station B may enhance their secrecy capacity. A central theme in the Maurer work is that noisy channels aid secrecy capacity. The results on secrecy capacity are extended further in [Maurer, U. and S. Wolf, “Unconditionally Secure Key Agreement and the Intrinsic Conditional Information,” IEEE Transactions on Information Theory, 45, No. 2, pp. 499-514, 1999].
Mobile Radio Channel
In 1995, Hershey and Hassan [Hershey, J. E., A. A. Hassan, and R. Yarlagadda, “Unconventional Cryptographic Keying Variable Management,” IEEE Transactions on Communications, 43, No. 1, pp. 3-6, January 1995.] proposed using an urban UHF channel that is highly time varying (multipath from mobile phones) to establish and securely distribute binary sequences. Their idea is to have Station A and Station B communicate in such a way that they measure the same multipath induced signal fading. Provided that the eavesdropper is not physically collocated with Station A or Station B, and the environment is dynamic and sufficiently complex—i.e., urban canyons—the eavesdropper has very little chance of observing or computing the same channel and thus measuring the same quantity. Their idea of using multipath for secure communication is developed further in [Hassan, A. A., W. E. Stark, J. E. Hershey, and S. Chennakeshu, “Cryptographic Key Agreement for Mobile Radio,” Digital Signal Processing, 6, pp. 207-212, 1996. and [KH000].
Other literature relating in general to this background information include:    Buscher, D. F.; Armstrong, J. T., Hummel, C. A., Quirrenbach, A., Mozurkewich, D., Johnston, K. J., Denison, C. S., Colavita, M. M., & Shao, M. “Interferometric seeing measurements on Mt. Wilson: power spectra and outer scales”. Applied Optics 34: 1081-1096. February 1995.    Bennett, C. H. and G. Brassard, “Quantum public key distribution system,” IBM Technical Disclosure Bulletin, 28, 1985, pp. 3153-3163.    Bennett, C. H., G. Brassard, C. Crepeau, and U. M. Maurer, “Generalized Privacy Amplification,” IEEE Transactions on Information Theory, 41, 1995, pp. 1915-1935.    Bennett, C. H., G. Brassard and J.-M. Robert, “Privacy amplification by public discussion,” SIAM Journal on Computing. 17, 210-229, 1988.    Brassard, G. and L. Salvail, “Secret key reconciliation by public discussion,” in Advances in Cryptology: Eurocrypt'93 Proceedings, pp. 410-423, 1993.    Clifford, S. F., “Temporal-frequency Spectra for a Spherical wave Propagating Through Atmospheric turbulence,” J. Optical Soc. Am., V. 61, N. 10, pp. 1285-1292, 1971.    Colavita, M. M.; Shao, M., & Staelin, D. H. “Atmospheric phase measurements with the Mark III stellar interferometer”. Applied Optics 26: 4106-4112. October 1987.    Imre Csiszar and Prakash Narayan, Secrecy Capacities for Multiterminal Channel Models, in IEEE International Symposium on Information Theory, 2007.    Dana, R. A. and L. A. Wittwer, “A General Channel Model for RF Propagation Through Structured Ionization,” Radio Science, 26, No. 4, pp. 1059-1068, July-August 1991.    Fried, D. L. “Statistics of a Geometric Representation of Wavefront Distortion”. Optical Society of America Journal 55: 1427-1435. 1965.    Hershey, J. E., A. A. Hassan, and R. Yarlagadda, “Unconventional Cryptographic Keying Variable Management,” IEEE Transactions on Communications, 43, No. 1, pp. 3-6, January 1995.    Hughes, R. J., Nordholt, J. E., Derkacs, D. and Peterson, G., “Practical free-space quantum key distribution over 10 km in daylight and at night,” New Journal of Physics 4 (2002) Published 12 Jul. 2002.    Ishimura, A., “Wave Propagation and Scattering in Random Media,” IEEE Press, 1978, pp. 381-385.    Janwa, Heeralal and Moreno, Oscar, “McEliese Public Key Cryptosystems Using Algebraic-Geometric Codes,” Designs, Codes and Cryptography, Vol. 8, No. 3, June 1996.    Kolmogorov, A. N. “Dissipation of energy in the locally isotropic turbulence”. Comptes rendus (Doklady) de l'Academie des Sciences de l'U.R.S.S. 32: 16-18. 1941.    Kolmogorov, A. N. “The local structure of turbulence in incompressible viscous fluid for very large Reynold's numbers”. Comptes rendus (Doklady) de l'Academie des Sciences de l'U.R.S.S. 30: 301-305. 1941.    Kazovsky, L. G., “Balanced Phase-Locked Loops for Optical Homodyne Receivers: Performance Analysis, Design Considerations, and Laser Linewidth Requirements,” Journal of Lightwave Technology, Vol. LT-4, No. 2, February 1986, pp. 182-195.    Knepp, D. L. and W. A. Brown, “Average Received Signal Power After Two-way Radar Propagation Through Ionized Turbulence,” Radio Science, 37, No. 4, pp. 1575-1596, July-August 1997.    H. Koorapaty, A. A. Hassan and S. Chennakeshu, “Secure Information Transmission for Mobile Radio,” IEEE Communications Letters, 4, No. 2, pp. 52-55, February 2000.    Lo, H.-K., “Method For Decoupling Error Correction From Privacy Amplification,” Preprint quant-ph/0201030, 2002.    Maurer, U., “Perfect Cryptographic Security from Partially Independent Channels,” Proceedings of the 23rd ACM Symposium on Theory of Computing (STOC), pp. 561-572, 1991.    Marcikic, I., Lamas-Linares, A., and Kurtsiefer, C., “Free-space quantum key distribution with entangled photons,” arXiv:quant-ph/0606072 v2 3 August 2006.    Noll, R. J. “Zernike polynomials and atmospheric turbulence”. Optical Society of America Journal 66: 207-211. March 1976.    Nightingale, N. S.; Buscher, D. F. “Interferometric seeing measurements at the La Palma Observatory”. Monthly Notices of the Royal Astronomical Society 251: 155-166. July 1991.    O'Byrne, J. W. “Seeing measurements using a shearing interferometer”. Publications of the Astronomical Society of the Pacific 100: 1169-1177. September 1988.    Ozarow, L. H. and A. D. Wyner, “Wire-Tap Channel II,” Bell Labs Technical Journal, 63, pp. 2135-2157, December 1984.    Peterson, C. G., “Fast, efficient error reconciliation for quantum cryptography.” Preprint quant-ph/0203096, 2002.    Tatarski, V. I. Wave Propagation in a Turbulent Medium. McGraw-Hill Books. 1961.    Gilles Van Assche, Jean Cardinal, and Nicolas J. Cerf, Reconciliation of a quantum-distributed Gaussian key, IEEE Transactions on Information Theory, 50(2):394-400, 2004.    M. Bloch, A. Thangaraj, S. McLaughlin, and J.-M. Merolla, LDPC-based secret key agreement over the Gaussian wiretap channel, in IEEE International Symposium on Information Theory, 2006.    Joao Barros and Miguel R. D. Rodrigues, Secrecy Capacity of Wireless Channels, in IEEE International Symposium on Information Theory, 2006.    S. K. Leung-Yan-Cheong and M. E. Hellman, The gaussian wire-tap channel, IEEE Transactions on Information Theory, 24(4): 451-456, 1978.    Ueli M. Maurer, Secret key agreement by public discussion from common information, IEEE Transactions on Information Theory, 39(3):733-742, 1993.    Ueli M. Maurer and Stefan Wolf, Towards Characterizing When Information-Theoretic Secret Key Agreement Is Possible, in ASIACRYPT, Kwangjo Kim and Tsutomu Matsumoto eds, volume 1163 of Lecture Notes in Computer Science, pp. 196-209, Springer 1996.    [RW03] Renato Renner and Stefan Wolf, New Bounds in Secret-Key Agreement: The Gap between Formation and Secrecy Extraction, in EUROCRYPT, Eli Biham ed., volume 2656 of Lecture Notes in Computer Science, pp. 562-577, Springer, 2003.    Renato Renner and Stefan Wolf, Simple and Tight Bounds for Information Reconciliation and Privacy Amplification, in ASIACRYPT, Bimal K. Roy ed., volume 3788 of Lecture Notes in Computer Science, pp. 199-216, Springer, 2005.    Shengli Liu, Van Tilborg, Henk C. A. and Van Dijk, M., “Practical Protocol for Advantage Distillation and Information Reconciliation,” Designs, Codes and Cryptography, Volume, 30, Number 1, August 2003.